// #define _CRT_SECURE_NO_WARNINGS 1	
// #include"SeqList.h"  //为什么包了自定义头文件，就会报错？


#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLDatatype;	//顺序表类型
typedef struct SeqListInfo	//基本结构
{
	SLDatatype* data;	//数据
	size_t size;	//实际有效数据数
	size_t capacity;	//容量
}SL;

void SeqListInit(SL* ps);	//顺序表初始化
void SeqListDestroy(SL* ps);	//销毁顺序表

void SeqListPrint(SL* ps);	//打印顺序表

void SeqListPushBack(SL* ps, SLDatatype x);		//尾插
void SeqListPopBack(SL* ps);	//尾删

void SeqListPushFront(SL* ps, SLDatatype x);		//头插
void SeqListPopFront(SL* ps);	//头删

void SeqListInsert(SL* ps, int pos, SLDatatype x);	//任意插
void SeqListErase(SL* ps, int pos);	//任意位置删除

int SeqListFind(SL* ps, SLDatatype x);	//查找元素

// #define _CRT_SECURE_NO_WARNINGS 1	
// #include"SeqList.h"

void SeqListInit(SL* ps)	//顺序表初始化
{
	assert(ps);
	ps->data = NULL;	//指针置空
	ps->size = ps->capacity = 0;	//数据、容量归零
}

void SeqListDestroy(SL* ps)	//销毁顺序表
{
	assert(ps);
	free(ps->data);	//直接释放顺序表数据域
	SeqListInit(ps);	//代码复用
}

void SeqListPrint(SL* ps)	//打印顺序表
{
	assert(ps);
	size_t i = 0;	//定义一个同样类型的变量i
	//配合size进行打印
	for (i = 0; i < ps->size; i++)
		printf("%d ", ps->data[i]);	//ps->data[i]相当于我们熟悉的arr[i]
	printf("\n");	//全部输出结束后，可以换行
}

void decideCapacity(SL* ps)	//判断容量
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//两倍扩容
		SLDatatype* tmp = (SLDatatype*)realloc(ps->data, sizeof(SLDatatype) * newcapacity);
		assert(tmp);	//断言，可能存在扩容失败的情况
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
}
void SeqListPushBack(SL* ps, SLDatatype x)		//尾插
{
	assert(ps);
	decideCapacity(ps);	//判断是否需要扩容

	ps->data[ps->size++] = x;	//尾插成功
	//SeqListInsert(ps, ps->size, x);	//可以使用任意位置插入，替代插入
}

void SeqListPopBack(SL* ps)	//尾删
{
	assert(ps);
	assert(ps->size > 0);	//需要断言一下，如果顺序表本来一个元素都没有，是肯定删不了的
	ps->size--;	//有效数据-1，就是尾删
	//SeqListErase(ps, ps->size - 1);	//可以使用任意位置删除，替代删除
}

void SeqListPushFront(SL* ps, SLDatatype x)		//头插
{
	assert(ps);	//断言，防止空指针
	decideCapacity(ps);	//判断扩容

	//先把数据整体往后挪动，再头插
	size_t end = ps->size;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}
	ps->data[end] = x;
	ps->size++;
	//SeqListInsert(ps, 0, x);	//可以使用任意位置插入，替代插入
}

void SeqListPopFront(SL* ps)	//头删
{
	assert(ps);
	assert(ps->size > 0);

	//同头插原理一样，需要把数据整体往前挪动
	size_t begin = 0;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;	//有效元素-1，就可以实现头删
	//SeqListErase(ps, 0);	//可以使用任意位置删除，替代删除
}

void SeqListInsert(SL* ps, int pos, SLDatatype x)	//任意插
{
	assert(ps);
	assert(pos >= 0);
	assert((size_t)pos <= ps->size);
	decideCapacity(ps);	//判断容量

	//原理有点类似头插，不过终止条件依赖于pos
	size_t end = ps->size;
	while (end > (size_t)pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)	//任意位置删除
{
	assert(ps);
	assert(pos >= 0);
	assert((size_t)pos < ps->size);

	//类似于头删
	size_t begin = (size_t)pos;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;
}

int SeqListFind(SL* ps, SLDatatype x)	//查找元素
{
	assert(ps);
	size_t i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
			return i;
	}

	return -1;	//没有找到目标元素
}

//void TestSeqList1()
//{
//	SL s;
//	SeqListInit(&s);
//
//	SeqListPushBack(&s, 1);
//	SeqListPushBack(&s, 2);
//	SeqListPushBack(&s, 3);
//	SeqListPrint(&s);
//
//	SeqListPushFront(&s, 4);
//	SeqListPushFront(&s, 5);
//	SeqListPushFront(&s, 6);
//	SeqListPrint(&s);
//
//	SeqListInsert(&s, 0, 200);	//实现头插
//	SeqListInsert(&s, s.size, 100);	//实现尾插
//	SeqListPrint(&s);
//
//	SeqListErase(&s, 0);	//实现头删
//	SeqListErase(&s, s.size - 1);	//实现尾删
//	SeqListPrint(&s);
//
//	SLDatatype x = 0;
//	printf("请输入你想删除的元素:>");
//	scanf("%d", &x);
//	SeqListErase(&s, SeqListFind(&s, x));
//	SeqListPrint(&s);
//
//	SeqListDestroy(&s);
//}

void menu()
{
	printf("*******************************\n");
	printf("******  0.退出   1.打印  ******\n");
	printf("******  2.尾插   3.尾删  ******\n");
	printf("******  4.头插   5.头删  ******\n");
	printf("******  6.任意插 7.任意删******\n");
	printf("******  8.按元素值插入   ******\n");
	printf("******  9.按元素值删除   ******\n");
	printf("*******************************\n");
}

int main()
{
	int input = 1;
	SL s;
	SeqListInit(&s);	//创建一个顺序表
	while (input)
	{
		int pos = 0;
		SLDatatype x = 0;
		SLDatatype y = 0;
		menu();
		printf("请选择:>");
		scanf("%d", &input);
		switch (input)
		{
		case 0:
			printf("退出顺序表!\n");
			SeqListDestroy(&s);
			break;
		case 1:
			SeqListPrint(&s);
			break;
		case 2:
			printf("请输入一个值:>");
			scanf("%d", &x);
			SeqListPushBack(&s, x);
			break;
		case 3:
			SeqListPopBack(&s);
			break;
		case 4:
			printf("请输入一个值:>");
			scanf("%d", &x);
			SeqListPushFront(&s, x);
			break;
		case 5:
			SeqListPopFront(&s);
			break;
		case 6:
			printf("请输入下标和目标值:>");
			scanf("%d %d", &pos, &x);
			SeqListInsert(&s, pos, x);
			break;
		case 7:
			printf("请输入下标:>");
			scanf("%d", &pos);
			SeqListErase(&s, pos);
			break;
		case 8:
			printf("请输入待插入元素值和目标值:>");
			scanf("%d %d", &y, &x);
			SeqListInsert(&s, SeqListFind(&s, y), x);
			break;
		case 9:
			printf("请输入待删除元素值:>");
			scanf("%d", &y);
			SeqListErase(&s, SeqListFind(&s, y));
			break;
		default :
			printf("选择错误，请重新选择!\n");
			break;
		}
	}
	return 0;
}